package main

import "fmt"

func main213() {
	arr := []int{12, 12, 2332, 12, 121, 233, 12, 2, 23, 5765}

	MergeSort(arr, 0, len(arr)-1)
	fmt.Println(arr)
}

// 可以划分为子空间问题，即递归
func MergeSort(arr []int, l int, r int) {

	if l < r {
		// 用于整个
		mid := (l + r) / 2
		MergeSort(arr, l, mid)
		// 不会出现区间重叠的情况
		MergeSort(arr, mid+1, r)
		Merge(arr, l, mid, r)
	}

}

// 归并时也是边界情况，归并时对边界情况的处理很经典
func Merge(arr []int, l int, mid int, r int) {
	temp := make([]int, r-l+1)
	// mid划分为temp1
	len1 := mid - l + 1
	len2 := r - mid
	temp1 := make([]int, len1)
	temp2 := make([]int, len2)
	copy(temp1[0:len1], arr[l:mid+1])
	copy(temp2[0:len2], arr[mid+1:r+1])
	i := 0
	j := 0

	// 将不熟悉的直接转换为熟悉的
	for i < len1 && j < len2 {
		if temp1[i] > temp2[j] {
			temp[i+j] = temp2[j]
			j++
		} else {
			temp[i+j] = temp1[i]
			i++
		}
	}

	for i < len1 {
		temp[i+j] = temp1[i]
		i++
	}
	for j < len2 {
		temp[i+j] = temp2[j]
		j++
	}
	copy(arr[l:r+1], temp[0:len(temp)])
	

}

// 在归并时不是交换，则必定有额外的空间
func Merge2(arr []int, l1 int, r1 int, l2 int, r2 int, temp []int) {
	// 赋值
	size := r2 - l1 + 1
	copy(temp[0:size], arr[l1:r2+1])
	i := 0
	j := 0
	for i < r1-l1 && j < r2-l2 {
		// 凭空多出很多变量
		if temp[i] > temp[r1-l1+1+j] {
			// arr不是从零开始
			arr[l1+i+j] = temp[r1-l1+1+j]
			j++
		} else {
			arr[l1+i+j] = temp[i]
			i++
		}
	}
	for i < r1-l1 {
		arr[l1+i+j] = temp[i]
		i++
	}
	for j < r2-l2 {
		arr[l1+i+j] = temp[r1-l1+1+j]
		j++
	}

}
